打的好cha，最近疯狂吃shit
E. Intercity Travelling
题意
x轴正向有长度n的公路，$1$ ~ $n-1$每个点都有可能有加油站(显然共有 $2^{n-1}$种可能)，每次到了一个加油站就要从1开始从新，每个距离的贡献为$a_i(1<=i<=n)$,问总贡献的期望值 × $2^{n-1}$ % 998244353
题解
考虑 $2^{n-1}$ 种情况，每个$a_i$的贡献次数都是确定的，故算出每个数的贡献即可，但是每个$a_i$出现的次数怎么算？
这个没想到怎么算？
反过来，我们考虑每个位置对于每个$a_i$出现的概率，因为每个位置是否安置加油站的概率都是1/2，故可以递推出每个位置可能的$a_i$的概率，再× $2^{n-1}$即可
推导过程：
1 | ... |